import java.util.*;

public class Solution1439 {
    public int kthSmallest(int[][] mat, int k) {
        PriorityQueue<int[]> priorityQueue=new PriorityQueue<>((a,b)->{
            int x=0,y=0;
            for (int i=0;i<mat.length;i++){
                x+=mat[i][a[i]];
                y+=mat[i][b[i]];
            }
            return x-y;
        });
        Set<List<Integer>> set=new HashSet<>();
        int[] first=new int[mat.length];
        priorityQueue.offer(first);
        set.add(toList(first));
        for (int i=0;i<k-1;i++){
            int[] q=priorityQueue.poll();
            for (int j=0;j<mat.length;j++){
                int[] n=Arrays.copyOf(q,mat.length);
                n[j]=q[j]+1;
                if (n[j]<mat[0].length && !set.contains(toList(n))){
                    priorityQueue.offer(n);
                    set.add(toList(n));
                }
            }
        }
        int[] p=priorityQueue.poll();
        int ans=0;
        for (int i=0;i<mat.length;i++){
            ans+=mat[i][p[i]];
        }
        return ans;
    }

    private List<Integer> toList(int[] a) {
        List<Integer> t=new ArrayList<>();
        for (int i : a) {
            t.add(i);
        }
        return t;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1439().kthSmallest(new int[][]{{1,3,11},{2,4,6}},9));
    }
}
